package com.leecode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Set;

/**
 * 56. 合并区间
 * 给出一个区间的集合，请合并所有重叠的区间。
 * 示例 1:
 * 输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出: [[1,6],[8,10],[15,18]]
 * 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 */
public class Leet56 {
	public static void main(String[] args) {
//		new Leet56().merge(new int[][]{{1,3},{2,6},{8,10},{15,18}});
		new Leet56().merge(new int[][]{{5, 5}, {1, 3}, {3, 5}, {4, 6}, {1, 1}, {3, 3}, {5, 6}, {3, 3}, {2, 4}, {0, 0}});
	}

	/**
	 * 89%,97%,想想第一次为啥没有做出来,1.没有想到先排序;2.居然想原地(给自己加难度加到gg)总结考点如下
	 * 考点:排序+lambda
	 */
	public int[][] merge(int[][] intervals) {
		if (intervals.length < 2) return intervals;//边界,结束

		Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);//
		int[][] res = new int[intervals.length][2];
		int resIdx = 0;
		res[resIdx] = intervals[resIdx];
		for (int a = 1; a < intervals.length; a++) {
			int[] cur = intervals[a];
			if (res[resIdx][1] < intervals[a][0]) {
				res[++resIdx] = cur;//不合并
			} else {
				res[resIdx][1] = Math.max(res[resIdx][1], cur[1]);
			}
		}

		int[][] ints = Arrays.copyOf(res, resIdx + 1);

		return ints;
	}
}
